This tag is for basic 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 (5)

0
votes
0answers
33 views

Number of solutions to equation

I need to find the number of possible solutions to the equation x1+x2+x3+x4=9 where x1,x2,x3,x4 are natural numbers (including 0) and none of them are equal to 4 or 5. Checking with this: ...
3
votes
2answers
33 views

Partitions without 2

How do I find the generating function for partitions of $n$ that have no part with size $2$? In general, how would I find this for partitions that have no part of size $k$?
1
vote
0answers
43 views

Filling a square table with numbers

Suppose we have integers from $1$ to $q$ and a square table of $p$ rows. Let $q \leq p^2$. Denote $C_i$ to be $i$-th column of the table. The table is filled with numbers from $1$ to $q$ in such way ...
0
votes
1answer
42 views

Sum problem - distinct sum from 1 to n [closed]

I have problem: I have n numbers from 1 do n and I have: 1 + 2, 1 + 2 + 3, 2 + 3, 2 + 4 + ... + n and etc. I want to combine these numbers to get distinc sum. What is the minimum n, for which I get ...
2
votes
2answers
50 views

The smallest $n$ for which the sum of binomial coefficients exceeds $31$

I have a problem with the binomial theorem. What is the result of solving this inequality: $$ \binom{n}{1} + \binom{n}{2} + \binom{n}{3} + \cdots +\binom{n}{n} > 31 $$
2
votes
1answer
47 views

Number of unlabeled simple graphs with $n$ nodes even for all $ n\ge 5$?

The extended version of OEIS for the number of unlabeled simple graphs with $n$ nodes shows that the only odd number (besides the trivial cases $n = 0 $ and $n = 1$) is for $n=4$ ($11$ graphs). The ...
1
vote
0answers
46 views

n bins, m balls and m>n: Probability of at least r bin containing exactly k balls.When bins are numeret from 1…n and ball is equale.

I want to calculate this probability .In this question $N$ bins, $m$ balls: Probability of any bin containing *exactly* $k$ balls. calculate this but I can not understand this calculation.To be more ...
-1
votes
1answer
16 views

Question on probability of fail rolling several dices [closed]

Sorry for so easy question. I have a success condition on rolling more than 2 (3,4,5,6) on 6 sided dice. Which probability on failing this condition 3 or more times rolling six dices?
0
votes
2answers
27 views

I am kind of confused on how to solve this question. Can anyone help please

If we let $S$ be the set that is defined by the following two rules: 1 is an element of the set $s$ If $s$ is an element of the set $s$, then x+$2 \sqrt{x}+1$ is also an element of the set $s$ how ...
-1
votes
1answer
36 views

Prove that exists such sequence…

Given is a set of number: $$ {a_1, ... , a_{11} } $$ Prove that there exists a sequence of non-zero, that $$ x_1, ..., x_ {11} $$ of words from the set {1,0,1} that the number of: $$ x_1a_1 + ... + ...
0
votes
1answer
73 views

COmbinatoric : Guess who is the winner candidate?

National Radio Broadcast will put a contest to guess five winners out of twelve local boxers who will compete to win the best 5 boxers. All twelve boxers are equally good so the chance of winning is ...
0
votes
0answers
26 views

Number of matrices based on Hamming distance

Given a set $S$ of all possible binary matrices of order $n\times2^n$ where $n\in N$. We can name the matrices as $M_i$ where i is the decimal representation of the binary string of length $n\cdot ...
0
votes
2answers
35 views

Ball Occupancy Problem

Suppose we put r balls at random in n boxes, i.e., all n r assignments of balls to boxes have equal probability. Let Ai be the event that the ith box is empty and Nn = the number of empty boxes. It is ...
0
votes
1answer
15 views

How many 4-digit integers greater than zero have 3 or 6 as their third digit and 3 as their first digit?

Questions like these are very common on PSAT and SAT tests, and I can never figure it out within a suitable amount of time. Is there an easier way to work through these kinds of problems without ...
1
vote
3answers
82 views

Permutations and Combinations? 3 digit number…

1) Make a 3 digit even number without repeated digits, using 0, 4, 5 , 6, 7. Also the first digit cannot be 0. 2)Arrange 12 books in a line, 4 of which are english, 3 of which are science, and 5 ...
0
votes
1answer
71 views

Permutations and Combinations. Arranging things to be adjacent etc…

How many ways to do the following tasks 1)Arrange 12 blocks in a line, 4 of which are green, 3 of which are blue, and 5 red, so that all blocks are adjacent. 2)Form an 8 digit number using each ...
2
votes
0answers
42 views

s4≀s2 visually?

What does the polytope whose symmetry is (exactly, not larger isomorphisms) s4≀s2 look like? Does anyone know of a full decomposition of its construction, i.e. lattices, hasse diagrams, cayley graphs, ...
0
votes
1answer
52 views

Combinations Problem - Arranging People in Rooms

A hostel has four vacant rooms. Each room can accommodate a maximum of four people. In how many different ways can six people be accommodated in four rooms. The answer is 4020. My case by case ...
0
votes
2answers
44 views

sum of the numbers of both subsets are equal.

Given a set of 10 numbers chosen from {10,11,...,99}. Prove that in this set there are two non-empty and different subsets such that the sum of the numbers of both subsets are equal. Please for ...
3
votes
3answers
54 views

Prove $\sum_{k=0}^{n}\frac{\binom{n}{k}(-1)^k}{k+1}$ = $\frac{1}{n+1}$

Any tips on where to start? I tried induction, using the inductive property of Binomial coefficients and the Mean Value Theorem for divided differences however I haven't made any progress.
2
votes
2answers
30 views

Prove that, given any positive integer n, some multiple of it must be of the form 99…900…0

Prove that, given any positive integer n, some multiple of it must be of the form 99...900...0 Give me a hand, please.
1
vote
1answer
31 views

octagonal number theorem $q$-Pochhammer symbol expression

Setting the exponents of this analogue of the series in Euler's Pentagonal Number theorem to be the octagonal numbers: $$U(q)= \sum_{n\in\mathbb{Z}} (-1)^{n}q^{n(6n-4)/2}$$ in mpmath: ...
0
votes
0answers
15 views

Number of solutions for a multiple traveling salesman (mTSP) problem

Traveling salesman problem (TSP) with n-number of cities and only one salesman has "nPn" solutions which is n! but when you have more than one salesman, say k-number salesman, to travel n-number of ...
1
vote
3answers
61 views

$2^n$ binomial theorem

How can I prove that $$2^n=2\left({n \choose 0}+{n \choose 2}+{n \choose 4}+\dots\right)$$ using the binomial theorem. I've tried expanding $(x-y)^n$ with multiple different values of $x$ and $y$ but ...
3
votes
1answer
46 views

solving a combinatorial problem

Alex has $N$ dice; each of them has $K$ faces numbered from $1$ to $K$. Now he has arranged the $N$ dice in a line. He can rotate/flip any die if he wants. How many ways he can set the top faces such ...
2
votes
1answer
66 views
+100

A Law of Large Numbers Without Replacement

Let $(n_1,...,n_r)$ be $r$ positive integers, and let $n=n_1+...+n_r$. Fo each positive integer $m$ consider an urn containing $mn$ balls, of which $mn_1$ are of type 1,..., $mn_r$ of type r. For each ...
0
votes
1answer
22 views

Proving a combination problem?

Given n and r are positive integers, how should I go about proving this statement? I tried using the combination forumula but I didnt really came close of solving it. Any help is appreciated. ...
1
vote
1answer
43 views

$O(1)$ algorithm for coin change w/out nickels

For the coin changing problem in the case without nickels (only quarters, dimes, and pennies available), assuming you use quarters until $x < 50$ since it's better to use quarters for $x \geq 50$; ...
3
votes
2answers
47 views

Expected number of cycles in permutation

Consider a random permutation of $1,2,\ldots,n$. What is the expected number of cycles in it? I thought about using linearity of expectation, but here it's not clear how we can break down the main ...
0
votes
0answers
18 views

Properties of the 'forgotten' symmetric polynomials

In I.G. Mcdonald "Symmetric Functions and Hall Polynomials" pg.22, the forgotten symmetric functions 'f' are introduced very briefly as the result of applying an involution w to the monomial symmetric ...
1
vote
1answer
20 views

Question regarding an algebraic manipulation in GFology

How does the author arrive at the last equality in the first line, i.e.$$\text{why is } [x^k]\frac{1}{1-y(1+x)} = \frac{1}{1-y}[x^k]\frac{1}{1-\left(\frac{y}{1-y}\right)x} \text{?}$$
1
vote
1answer
81 views

combination/induction question, number of ways you can divide n people into groups of 1 or 2

this is homework!! Let $n \geq 1$ be an integer and consider $n$ people $P_1,P_2,\ldots,P_n$. Let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group ...
0
votes
3answers
34 views

Ways of spending money combinatorial problem

Suppose person X has $12$ dollars.In each of the first 5 days he buys one of the following items. 1.Item A for $1 2.Item B for $2 3.Item C for $3. In how many ways can he spend the money ...
0
votes
0answers
17 views

Combinatorial proof of an identity of Striling number of first kind

I can prove this identity using induction but i was looking for a combinatorial proof for this identity regarding stirling numbers of first kind. How should i proceed? Where, Thanks in advance.
5
votes
0answers
90 views

Number of restricted ways to two-color a necklace [duplicate]

There are $n$ beads placed on a circle, $n\ge 3$. They are numbered in random order as viewed clockwise. Beads for which the number of the previous bead is less than the number of a next bead are ...
0
votes
0answers
51 views

A problem related to combinatorics

If we choose $r$ objects from $n$ objects, where every combination of objects always contains a particular object, the number of ways for such a choice equals $C(n-1,r-1)$. Can someone explain why? ...
4
votes
1answer
66 views

No. of integral solutions of $x_1+x_2+x_3+x_4=20.$

I've to solve a no. of questions of this type but don't get how to do it: Determine the no. of integral solutions of $x_1+x_2+x_3+x_4=20.$ given the constraint that $$1\leq x_1\leq ...
1
vote
2answers
43 views

Number of ways to group digits in {1,2,3,4,5,6,7,8,9} into numbers, while maintaining order

I have a set of integers from 1 to 9, call it A: $$A=[1,2,3,4,5,6,7,8,9]$$ How could I find the total number of possible combination of numbers within that set, while maintaining order? For example, ...
2
votes
2answers
43 views

How many 7-digit telephone numbers have an odd number of even numbers?

((7 choose 1)*5^7) + (7 choose 3)*5^7) + (7 choose 3)*5^7) + (7 choose 1)*5^7) This is how I attempted to solve the problem, but I'm not sure if its correct.
7
votes
1answer
61 views

Sets of size at least $k$ with intersection of size at most $1$ cool problem.

At the OMM School every student goes to at least $k$ classes and two classes have at most $1$ student in common. Prove there is a set of $k$ classes where all of those classes have the same amount of ...
3
votes
2answers
62 views

$P(AB=BA)$ , $A,B\in M_{3x3}(\mathbb Z/p\mathbb Z)$

Let $A,B\in M_{3x3}(\mathbb Z/p\mathbb Z)$ ($p$ a prime number). Find the probability $P$ that $AB=BA$ that is $P(AB=BA)$ $$A=\begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} ...
0
votes
3answers
39 views

Number of ways to park $10$ cars

Given $10$ cars (5 Fords, 3 Dodges, and 2 Hondas), how many ways can the cars be parked if there are (a) $10$ spots available? (b) $15$ spots available? My solution: (a) ${10 \choose 5} + {5 \choose ...
1
vote
2answers
12 views

Sum of Cells in Corner and in Center of Magic Square

For the magic square of order 4, the sum of 4 cells in each corner and sum of 4 cells in the center is the same which is equal to 34. But I don't have idea how to prove it. Any hint?
2
votes
1answer
34 views

On the number of cycles and independent edges in $K_{8}$

I am trying to find the number of cycles and $K_{2}$'s in $K_{8}$. That is, partition $8$ into all the ways such that the lowest part can be a $2$, so we have $8 = 8$, $6+2$, $5+3$, $2+3+3$, $4+4$, ...
0
votes
2answers
123 views

How many Binary numbers?

How many binary numbers of length $n$ can be generated where $n > 7$ and the number either start with $000$ or end with $111$? My questions is, can I choose an $n$ randomly? For example, let's say ...
0
votes
1answer
29 views

Combo: Unambiguous expression - String

I am stuck on finding an unambiguous express so that it can produce all the strings in the given set, for the set of binary strings where for each block of zero's which are of length minimum 3 must be ...
4
votes
0answers
55 views

Ordinary or Rational Generating Function for Associated Stirling Numbers $b(n,k)$

I am trying to identify or find the ordinary generating function (not the exponential generating function) for the Associated Stirling numbers of the Second kind, denoted $$b(1;n,k)=b(n,k)$$ These ...
7
votes
1answer
106 views

The meaning of a definition involving multiple sums with Bernoulli numbers

Reading a paper regarding Bernoulli numbers, and I stumbled onto a definition. First let $$\frac{x}{e^x-1}=\sum_{k=0}^{\infty}B_k\frac{x^k}{k!}$$ The author then goes on to define new terms. Let ...
1
vote
3answers
33 views

Total number of possibilities

I have 3 buckets, 1st bucket has 5 red balls, 2nd bucket has 3 green balls and 3rd one has 2 blue balls. so I have total 10 balls in 3 buckets. I need to know, what are the possible combination ...
2
votes
1answer
29 views

$\sum_{i=0}^n (-1)^i \delta_i(\sum_{j=0}^{n+1} (-1)^j \delta_j) = 0$, given that $\delta_i \delta_j = \delta_{j-1}\delta_i$ whenever $i < j$

$\sum_{i=0}^n (-1)^i \delta_i(\sum_{j=0}^{n+1} (-1)^j \delta_j) = 0$, given that $\delta_i \delta_j = \delta_{j-1}\delta_i$ whenever $i < j$ This problem shows up in the middle of dealing with ...