For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

1
vote
0answers
25 views

Choosing k pairs l distance apart from n numbers

I need to choose $k$ pairs of numbers out of first $n$ natural numbers such that the elements in each pair are $l$ distance apart. For example, if $n = 10, k = 3$ and $l = 2$, $\{(1,3),(4,6),(7,9)\}$ ...
1
vote
2answers
41 views

Number of arrangements in which not all the vowels are together

How many arrangements of the letters of the word ‘BENGALI’ can be made (i) If the vowels are never together. I dont want the solution by negation method. I have seen the solution on ...
3
votes
1answer
74 views

Multiple of $p$ in first $p+1$ Fibonacci Numbers

Defining $F_0 = F_1 = 1$ and $F_{n+1} = F_{n} + F_{n-1}$ for $n>0$ gives the Fibonacci sequence, and it is well-known that modulo $p$, one of the first $p+1$ terms is $0.$ In fact, more is known, ...
1
vote
1answer
42 views

(Combinatorics) number of compositions of $n$ into $k$ parts so that $i$-th part is not larger than $a_i$

Let $a_1,a_2,\ldots,a_k $ be non negative integers, and let $a(n)$ be the number of compositions of $n$ into $k$ parts so that $i$-th part is not larger than $a_i$. Find the ordinary generating ...
-1
votes
1answer
37 views

Possible outcomes [closed]

You have a set of marbles consisting of $4$ red, $3$ green, $2$ blue, $3$ orange, $2$ yellow, and $3$ purple marbles. How many sets of six marbles include at least one blue marble?
0
votes
1answer
54 views

An interesting combinatorial identity [duplicate]

I'm self studying Burton's number theory and came across the following problem: Prove that: $\binom{n}{1}+2\binom{n}{2}+\cdots+n\binom{n}{n}=n2^{n-1}$ So I tried expanding $n(1+b)^{n-1}$ with the ...
7
votes
3answers
110 views

Random Sequence of Alternating Increase/Decrease Numbers

The problem statement: Repeatedly pick a random number (uniformly-distributed) between $0$ and $1$. Keeping going while the second number is smaller than the first, the third number is larger than the ...
1
vote
1answer
93 views

A question in combinatorics

Given a sequence of $0$s and $1$s think of it as blocks of $0$s and $1$s. Like $0001101001$ is a sequence of blocks $000$,$11$,$0$,$1$,$00$,$1$ How may ways can one pick $t$ bits from a $0/1$ ...
0
votes
3answers
76 views

How many arrangements of the numbers satisfy a divisibility condition? [closed]

How many ways can one arrange the numbers 21,31,41,51,61,71,81 such that sum of every 4 consecutive numbers is divisible by 3 ?
1
vote
3answers
66 views

Prove $ \sum_{x=0}^n \binom{n}{x} = 2^n$ using binomial expansion? Right or wrong?

I am in a probability and statistics class. This is one of the first proofs we are supposed to do I am not sure where to start. I have done some research and I have seen proof by induction for ...
3
votes
3answers
83 views

Graph Theory - what are related fields in maths?

I am an undergraduate student who hoping to self teach Graph Theory. I have studied elementary graph theory before, and have recently started reading 'Bollobas - Modern Graph Theory'. What are your ...
2
votes
2answers
35 views

Counting nearly-sorted permutations

Let $[n]$ denote the set $\{1,2,\ldots,n\}$. We call a permutation $\sigma:[n]\to[n]$, $(n,k$)-nearly sorted if $$\forall i\in [n]: |\sigma(i) - i|\le k,$$ i.e., every element is shifted at most ...
2
votes
2answers
38 views

Write a number N as a sum of K numbers

I need to find the no of ways of partitioning a number N as a sum of K non-negative numbers. Zeroes are also needed to be included in the sum. Ordering does matter. Example- For $N=2,K=3 $ ...
1
vote
3answers
93 views

Finding the Closed Form of: $\sum\limits_{i=1}^n k\cdot{n-2 \choose k-2}$

I am stuck with this example in the textbook: find a closed form of: $$\sum\limits_{k=1}^n k\cdot{n-2 \choose k-2}.$$ I haven't found anything helpful on the web. Thanks for any advice.
0
votes
1answer
40 views

(combinatorics)Use compositional formula $G(x)$=$\sum_{n>=0}^\ g_n{x^n\over n!}$ ,and then find $g_n$

$g_n$=the number of ways of selecting a permutation of length n,and then selecting a cycle of that permutation. Use compositional formula $G(x)$=$\sum_{n>=0}^\ g_n{x^n\over n!}$ ,and then find ...
3
votes
1answer
49 views

Finding the number of primes numbers using exclusion/inclusion principle: What am I doing wrong?

I want to find the number of primes numbers between 1 and 30 using the exclusion and inclusion principle. This is what I got: The numbers in sky-blue are the ones I have to subtract. The others are ...
-2
votes
1answer
28 views

Stable matching solutions

The stable marriage problem is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A matching is a mapping from the ...
0
votes
1answer
52 views

How many pairs of consecutive integers? [closed]

How many pairs of consecutive integers? How many pairs of consecutive integers between and inclusive 1000 to 2000 is no carry required when the two integers added ? for example: 1001+1002=1003 is a ...
4
votes
3answers
191 views

Convolution of binomial coefficients

As part of a (SE) problem I've been working on, I came up with this expression: $$ \sum_{i=0}^M\binom{M-1+i}{i}\binom{M+i}{i} $$ I'd like to get a closed form for this, but after a considerable amount ...
2
votes
3answers
508 views

Why does “order matter” when calculating the probability that no people out of seven were born in winter?

SUMMARY Here's a problem from Harvard's Stats 110 course. For a group of 7 people, find the probability that all 4 seasons (winter, spring, summer, fall) occur at least once each among their ...
0
votes
1answer
45 views

How many possibilities of writing a natural number $M$ as a sum of $N$ natural numbers between $0$ and $M$?

How many possibilities are there of writing a natural number $M$ as a sum of $N$ natural numbers between $0$ and $M$? For example, I need to write $4$, using $4$ numbers between $0$ and $4$. The ...
0
votes
2answers
56 views

Probability of Poker Hands with Joker

Need help with a homework question: If a five card hand from a standard deck of 52 with an added joker (wildcard) is drawn: What is the probability that a hand contains at least one pair? ...
1
vote
2answers
59 views

Prove the coefficient of $x^2$ is the sum.

In the expansion: $(1 + ax)(1 + bx)(1+cx) \cdots$ find the general coefficient of $x^2$ and prove the formula. Consider $(1 + ax)(1 + bx)$, the coefficient of $x^2$ is: $ab$. Consider $(1 + ...
0
votes
5answers
88 views

$\sum_{i=0}^n {2n \choose 2i} = 2^{2n-1}$

$$ \sum_{i=0}^n {2n \choose 2i} = 2^{2n-1} $$ I know what this sum is supposed to equal. I also have a hint that I am supposed to use ${n \choose r} = {n-1 \choose r-1} + {n-1 \choose r}$ I was ...
1
vote
1answer
71 views

Min number of colors for shared light switches

I recently moved to a new house, and this house has more light switches than I'm used to. There a N lights in the house and M switches where N < M. A light may be controlled by 1 or more light ...
1
vote
1answer
66 views

Coefficient of operator and how to do it

This question stems from this $$ \frac{1}{x+z}- \frac{1}{x} = \sum_{k=0}^\infty \frac{z^k}{k!}\frac{d^k}{dx^k}[\frac{1}{x}] $$ Now, i need to find the Bell Polynomial of $\frac{1}{x}$, $$ ...
3
votes
4answers
87 views

Explain a couple steps in proof that ${n \choose r} = {n-1 \choose r-1} + {n-1 \choose r}$

Show ${n \choose r}$ = ${n-1 \choose r-1}$ + ${n-1 \choose r}$ I found a similar question on here but I am looking for a little bit more of an explanation on how they simplified Right Hand Side ...
0
votes
1answer
56 views

Counting increasing sequences with repetitions allowed

How to count number of increasing sequences of length $k$ where the first element can be $x_1$ ways, the second in $x_2$ ways and so on till $n$ and $n \geq k$. I am not able to solve this problem. ...
1
vote
3answers
25 views

Proving the number of leaves is larger by at least two than the number of vertices with a degree of at least 3

Prove that in every tree, the number of leaves is larger by at least two than the number of vertices with a degree of at least 3. Trying induction, I get something that is too short to be right, ...
0
votes
1answer
21 views

Find the number of multi-subsets of $M = \{r_1a_1,r_2a_2,…,r_na_n\}$

Find the number of multi-subsets of $M = \{r_1a_1,r_2a_2,...,r_na_n\}$. If someone is simply unaware of the term multi-subsets I am asking for the number of all combinations of $M$ where repetitions ...
1
vote
4answers
52 views

Subset lottery probability

Most lottery questions are exact, ie N numbers are winning, and you choose N numbers (chosen subset is as big as the winning subset). But how do you calculate the chance to win when you choose more ...
2
votes
3answers
53 views

Combinations and Permutations in ice cream cones… what is the difference?

The first two I am certain I have correct however c and d... I am struggling to understand the difference. I have done research on this site and have seen similar questions with explanations but I ...
0
votes
0answers
19 views

visiting $n$ distinct sites in a random walk of $n$ steps on $\mathbb{Z}^2$

Consider the symmetric random walk on $\mathbb{Z}^2$. I am looking for references about the number of ways to visit $n$ distinct sites in $n$ steps where I don't count the origin, so visiting $n+1$ ...
2
votes
0answers
29 views

Collection of subsets of a set with small overlap with each other

Consider a set with n elements. Consider a set S of subsets, each of fixed size k, with the property that any two subsets in S have intersection of size at most m-1 . In the following link Choosing ...
1
vote
2answers
102 views

Combination sum .

I want to evaluate the following sum : $$S(k,k')=\sum_{i} C_{i+k}^k C_{k'-i}^{k}$$ = $$S(k,k')=\sum_{i} \binom{i+k}{k} \binom{k'-i}{k}$$ I tried some steps but couldnt get further than : ...
3
votes
1answer
31 views

number of loops of length $n$ without crossings in random walk on $\mathbb{Z}^2$

Consider the symmetric random walk on $\mathbb{Z}^2$, where you go in one of the four directions with probability 1/4. We start in 0. My question is whether there are results on counting how many ways ...
7
votes
1answer
52 views

Partitioning $n$ naturals summing $2N$ into two sets summing $N$

I'm trying to solve this problem: Let $a_1, \ldots , a_n$ be natural numbers such that $a_k \le k$ for every $k = 1,\ldots,n$, and $\sum_{k=1}^{n} a_k=2N$. Show that there exists a partition of ...
0
votes
1answer
34 views

Binary tree bijection

I've been studying for an up coming exam in combinatorics and I came across something interesting by accident. We have the two combinatorial constructions: $$\mathbb{U}\cong SEQ(\mathbb{ZU})$$ And ...
-5
votes
0answers
62 views

Writing a given number as the sum of four triangular numbers

"Every number can be written as the sum of three triangular numbers. Can you prove it?"< this is the problem I have so far that: there are lots of numbers like 5 that cannot be written as the sum ...
6
votes
3answers
646 views

Arranging problem: 4 couples, 8 seats in a row… Am I making this too simple?

I am in a prob and stats course... haven't taken one in awhile and would like some help on these two problems. I think I am probably making these a little two simple. Four married couples have ...
3
votes
1answer
52 views

Dominos ($2 \times 1$ on $2 \times n$ and on $3 \times 2n$)

How many ways are there to tile dominos (with size $2 × 1$) on a grid of $2 × n$? How about on a grid of $3 × 2n$?
1
vote
1answer
36 views

Recursive random draw

Let $R(n)$ be a random draw of integers between $0$ and $n − 1$ (inclusive). I repeatedly apply $R$, starting at $10^{100}$. What’s the expected number of repeated applications until I get zero?
2
votes
0answers
36 views

Summation Formula Interpretation involving Roots of Unity

In a paper on Lacunary Recurrence Relations, D. H. Lehmer is beginning his preliminary information and presents the following sum formula: Let $p,q,r,s$ be positive integers, and let $n,t$ be ...
2
votes
1answer
61 views

Generalizing Hall's marriage theorem to arbitrary graphs

Given a finite graph G = (V, E) in which each vertex is a finite set, I call system of local representatives the choice for each vertex of one of its elements (the local representative), so that no ...
3
votes
2answers
72 views

Tangent numbers are divisible by $2^{n}$

Let us consider a $$\tan(z) = \sum_{n=1}^{\infty}{T_{2n-1} \cdot \frac{z^{2n-1}}{(2n-1)!}}$$. So, it can be shown that $$T_{2n+1}=\frac{(-1)^{n} 4^{n+1}(4^{n+1}-1) B_{2n+2}}{2n+2} $$ where $B_{2n+2}$ ...
3
votes
2answers
55 views

How many strings of $8$ English letters are there (repetition allowed)?

a) at least one vowel b) start with $x$ and at least one vowel c) start and end with $x$ and at least one vowel I can solve them easily by considering $total-no$ $vowel$. So, a) $26^8 -21^8$ b) ...
0
votes
1answer
32 views

How many strings of $3$ decimal digits have exactly two digits as $4$?

I approached the problem in this way : Fix two $4's$ and then third place can have $10$ ways to choose from {0,1,..,9} and then arrangement= ${10*3!}/2!$ = 30But , Since we have {$4,4,4$} and ...
2
votes
1answer
31 views

polynomial representing a self-orthogonal latin square

I need to show that for $q$, a prime power not equal to 2 or 3, the polynomial $f(x,y) = \lambda x+(1-\lambda)y$ represents a self-orthogonal latin square of order $q$, where $\lambda \in F_{q}$ is ...
0
votes
2answers
28 views

Space station, alarms, and malfunction

A space station has a set $A = \{A_1,A_2,A_3,A_4,A_5\}$ of 5 distinct alarms that indicates 3 abnormal conditions (without distinction between them). How many ways can the alarms be associated to the ...
2
votes
2answers
30 views

How to find the number of distinct combinations of a non distinct set of elements?

I'm trying to figure out a way to find the number of factors a number has based on its prime factorization without working out all the combinations. If the number breaks down into $n$ distinct prime ...